﻿namespace AdvancedTraining.Lesson04;

public class SubArrayMaxSumFollowUp
{
    private static int SubSqeMaxSumNoNext(int[]? arr)
    {
        if (arr == null || arr.Length == 0) return 0;
        if (arr.Length == 1) return arr[0];
        var dp = new int[arr.Length];
        // dp[i] : arr[0..i]挑选，满足不相邻设定的情况下，随意挑选，最大的累加和
        dp[0] = arr[0];
        dp[1] = Math.Max(arr[0], arr[1]);
        for (var i = 2; i < arr.Length; i++)
        {
            var p1 = dp[i - 1];
            var p2 = arr[i] + Math.Max(dp[i - 2], 0);
            dp[i] = Math.Max(p1, p2);
        }

        return dp[arr.Length - 1];
    }

    // 给定一个数组arr，在不能取相邻数的情况下，返回所有组合中的最大累加和
    // 思路：
    // 定义dp[i] : 表示arr[0...i]范围上，在不能取相邻数的情况下，返回所有组合中的最大累加和
    // 在arr[0...i]范围上，在不能取相邻数的情况下，得到的最大累加和，可能性分类：
    // 可能性 1) 选出的组合，不包含arr[i]。那么dp[i] = dp[i-1]
    // 比如，arr[0...i] = {3,4,-4}，最大累加和是不包含i位置数的时候
    //
    // 可能性 2) 选出的组合，只包含arr[i]。那么dp[i] = arr[i]
    // 比如，arr[0...i] = {-3,-4,4}，最大累加和是只包含i位置数的时候
    //
    // 可能性 3) 选出的组合，包含arr[i], 且包含arr[0...i-2]范围上的累加和。那么dp[i] = arr[i] + dp[i-2]
    // 比如，arr[0...i] = {3,1,4}，最大累加和是3和4组成的7，因为相邻不能选，所以i-1位置的数要跳过
    //
    // 综上所述：dp[i] = Max { dp[i-1], arr[i] , arr[i] + dp[i-2] }
    private static int MaxSum(int[]? arr)
    {
        if (arr == null || arr.Length == 0) return 0;
        var n = arr.Length;
        if (n == 1) return arr[0];
        if (n == 2) return Math.Max(arr[0], arr[1]);
        var dp = new int[n];
        dp[0] = arr[0];
        dp[1] = Math.Max(arr[0], arr[1]);
        for (var i = 2; i < n; i++) dp[i] = Math.Max(Math.Max(dp[i - 1], arr[i]), arr[i] + dp[i - 2]);
        return dp[n - 1];
    }

    /// <summary>
    /// 测试SubArrayMaxSumFollowUp算法
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("SubArrayMaxSumFollowUp算法测试开始...");

        // 测试用例1：基本功能测试
        var arr1 = new[] { 1, 2, 3, 1 };
        var result1SubSqe = SubSqeMaxSumNoNext(arr1);
        var result1Max = MaxSum(arr1);
        Console.WriteLine("测试1 - 基本功能:");
        Console.WriteLine($"数组: [1,2,3,1]");
        Console.WriteLine($"SubSqeMaxSumNoNext结果: {result1SubSqe} (期望: 4, 选择1和3)");
        Console.WriteLine($"MaxSum结果: {result1Max} (期望: 4, 选择1和3)");

        // 测试用例2：包含负数
        var arr2 = new[] { 2, 7, 9, 3, 1 };
        var result2SubSqe = SubSqeMaxSumNoNext(arr2);
        var result2Max = MaxSum(arr2);
        Console.WriteLine("\n测试2 - 包含负数:");
        Console.WriteLine($"数组: [2,7,9,3,1]");
        Console.WriteLine($"SubSqeMaxSumNoNext结果: {result2SubSqe} (期望: 12, 选择2和9和1)");
        Console.WriteLine($"MaxSum结果: {result2Max} (期望: 12, 选择2和9和1)");

        // 测试用例3：全负数
        var arr3 = new[] { -1, -2, -3, -4 };
        var result3SubSqe = SubSqeMaxSumNoNext(arr3);
        var result3Max = MaxSum(arr3);
        Console.WriteLine("\n测试3 - 全负数:");
        Console.WriteLine($"数组: [-1,-2,-3,-4]");
        Console.WriteLine($"SubSqeMaxSumNoNext结果: {result3SubSqe} (期望: -1, 选择-1)");
        Console.WriteLine($"MaxSum结果: {result3Max} (期望: -1, 选择-1)");

        // 测试用例4：单个元素
        var arr4 = new[] { 5 };
        var result4SubSqe = SubSqeMaxSumNoNext(arr4);
        var result4Max = MaxSum(arr4);
        Console.WriteLine("\n测试4 - 单个元素:");
        Console.WriteLine($"数组: [5]");
        Console.WriteLine($"SubSqeMaxSumNoNext结果: {result4SubSqe} (期望: 5)");
        Console.WriteLine($"MaxSum结果: {result4Max} (期望: 5)");

        // 测试用例5：两个元素
        var arr5 = new[] { 3, 5 };
        var result5SubSqe = SubSqeMaxSumNoNext(arr5);
        var result5Max = MaxSum(arr5);
        Console.WriteLine("\n测试5 - 两个元素:");
        Console.WriteLine($"数组: [3,5]");
        Console.WriteLine($"SubSqeMaxSumNoNext结果: {result5SubSqe} (期望: 5, 选择5)");
        Console.WriteLine($"MaxSum结果: {result5Max} (期望: 5, 选择5)");

        // 测试用例6：交替正负
        var arr6 = new[] { 1, -2, 3, -4, 5 };
        var result6SubSqe = SubSqeMaxSumNoNext(arr6);
        var result6Max = MaxSum(arr6);
        Console.WriteLine("\n测试6 - 交替正负:");
        Console.WriteLine($"数组: [1,-2,3,-4,5]");
        Console.WriteLine($"SubSqeMaxSumNoNext结果: {result6SubSqe} (期望: 9, 选择1、3、5)");
        Console.WriteLine($"MaxSum结果: {result6Max} (期望: 9, 选择1、3、5)");

        // 测试用例7：空数组
        int[]? arr7 = null;
        var result7SubSqe = SubSqeMaxSumNoNext(arr7);
        var result7Max = MaxSum(arr7);
        Console.WriteLine("\n测试7 - 空数组:");
        Console.WriteLine($"数组: null");
        Console.WriteLine($"SubSqeMaxSumNoNext结果: {result7SubSqe} (期望: 0)");
        Console.WriteLine($"MaxSum结果: {result7Max} (期望: 0)");

        // 测试用例8：空数组（空列表）
        var arr8 = Array.Empty<int>();
        var result8SubSqe = SubSqeMaxSumNoNext(arr8);
        var result8Max = MaxSum(arr8);
        Console.WriteLine("\n测试8 - 空数组（空列表）:");
        Console.WriteLine($"数组: []");
        Console.WriteLine($"SubSqeMaxSumNoNext结果: {result8SubSqe} (期望: 0)");
        Console.WriteLine($"MaxSum结果: {result8Max} (期望: 0)");

        Console.WriteLine("\nSubArrayMaxSumFollowUp算法测试完成!");
    }
}